/**
 19. 删除链表的倒数第 N 个结点
 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 进阶：你能尝试使用一趟扫描实现吗？

 示例 1：
 1->2->3->4->5


 输入：head = [1,2,3,4,5], n = 2
 输出：[1,2,3,5]

 示例 2：
 输入：head = [1], n = 1
 输出：[]

 示例 3：
 输入：head = [1,2], n = 1
 输出：[1]


 提示：
 链表中结点的数目为 sz
 1 <= sz <= 30
 0 <= Node.val <= 100
 1 <= n <= sz
 **/

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int i = 1;
        HashMap<Integer,ListNode> map = new HashMap<Integer, ListNode>();
        ListNode node = head;
        while (node != null){
            map.put(i,node);
            node = node.next;
            i++;
        }

        //倒数第 n-1 个
        ListNode nodePre = map.get(i-n-1);
        //倒数第 n 个
        if((i-n) == 1){
            return map.get(1).next;
        }else if(n == 1){
            nodePre.next = null;
        }else{
            nodePre.next = map.get(i-n + 1);
        }

        return head;
    }
}